Addition is exponentially harder than counting for shallow monotone circuits

摘要

Let $U_{k,N}$ denote the Boolean function which takes as input $k$ strings of$N$ bits each, representing $k$ numbers $a^{(1)},\dots,a^{(k)}$ in$\{0,1,\dots,2^{N}-1\}$, and outputs 1 if and only if $a^{(1)} + \cdots +a^{(k)} \geq 2^N.$ Let THR$_{t,n}$ denote a monotone unweighted threshold gate,i.e., the Boolean function which takes as input a single string $x \in\{0,1\}^n$ and outputs $1$ if and only if $x_1 + \cdots + x_n \geq t$. We referto circuits that are composed of THR gates as monotone majority circuits. The main result of this paper is an exponential lower bound on the size ofbounded-depth monotone majority circuits that compute $U_{k,N}$. Moreprecisely, we show that for any constant $d \geq 2$, any depth-$d$ monotonemajority circuit computing $U_{d,N}$ must have size$\smash{2^{\Omega(N^{1/d})}}$. Since $U_{k,N}$ can be computed by a singlemonotone weighted threshold gate (that uses exponentially large weights), ourlower bound implies that constant-depth monotone majority circuits requireexponential size to simulate monotone weighted threshold gates. This answers aquestion posed by Goldmann and Karpinski (STOC'93) and recently restated byHastad (2010, 2014). We also show that our lower bound is essentially bestpossible, by constructing a depth-$d$, size-$2^{O(N^{1/d})}$ monotone majoritycircuit for $U_{d,N}$. As a corollary of our lower bound, we significantly strengthen a classicaltheorem in circuit complexity due to Ajtai and Gurevich (JACM'87). Theyexhibited a monotone function that is in AC$^0$ but requires super-polynomialsize for any constant-depth monotone circuit composed of unbounded fan-in ANDand OR gates. We describe a monotone function that is in depth-$3$ AC$^0$ butrequires exponential size monotone circuits of any constant depth, even if thecircuits are composed of THR gates.